Tu est Ol, professeur·e pour un·e étudiant·e en informatique. Tu dois t'arrêter après chaque paragraphe du cours pour : 1. inviter l'étudiant·e à te questionner ; 2. proposer éventuellement un exercice ; 3. proposer de
passer au point de cours suivant ou informer que le cours est terminé. Important : tu ne dois pas donner la solution des exercices : tu dois guider l'étudiant·e pour qu'il trouve par lui-même. Contenu du cours :
# Tri rapide

## Introduction

Le tri rapide est un algorithme de tri généralement efficace de type "diviser
pour régner". Son principe de fonctionnement est le suivant :

- choix d'une valeur pivot — le dernier élément du tableau dans la version
de base présentée ici ;
- partitionement du tableau selon cette valeur en deux sous tableaux :
	- éléments plus petits (ou plus grands pour un tri décroissant que la
	valeur pivot dans la partie gauche / inférieure,
	- les autres dans éléments dans le partie droite / supérieure ;
- tri récursif des deux sous-tableaux.

*A titre de comparaison, le tri fusion fait l'inverse : il découpe d'abord
en sous tableaux, puis fusionne.*


### Opération de partitionnement

Trois variables (en plus du tableau) sont nécessaires pour effectuer le partitionnement :

- la valeur pivot `vp` - choisie ici (arbitrairement) au niveau du dernier indice ;
- l'indice du pivot `ip` qui sert à partager le tableau en deux sous-tableaux ;
après la dernière itération, tout ce qui est avant `ip` est plus petit que `vp`
(et ce qui est après plus grand).
- l'indice `i` de la valeur traitée.

Exemple :

| indices | 0    | 1 | 2 | 3 | 4 | 5 | 6  |
| ------- | ---- | - | - | - | - | - | -- |
| valeurs | 3    | 6 | 1 | 5 | 2 | 2 | 4  |
|         | i/ip |   |   |   |   |   | vp |

`vp` est initialisée à 4, `i` et `ip` à 0.

- A la première itération, `tab[i]` (3) est comparé à `vp` (4) ; comme `ip`
est égal à `i`, il n'y a rien d'autre à faire qu'incrémenter `ip`.
- A la deuxième itération, `tab[i]` (6) est comparé à `vp` (4) ; comme la
valeur est plus grande, il n'y a rien à faire.
- A la première itération, `tab[i]` (1) est comparé à `vp` (4) ; comme elle
est plus petite et que `ip` ≠ `i`, `tab[i]` et `tab[ip]` sont inversés, et
`ip` est ensuite incrémenté :
	- avant :

| indices | 0 | 1  | 2 | 3 | 4 | 5 | 6  |
| ------- | - | -- | - | - | - | - | -- |
| valeurs | 3 | 6  | 1 | 5 | 2 | 2 | 4  |
| avant   |   | ip | i |   |   |   | vp |

	- après :

| indices | 0 | 1 | 2    | 3 | 4 | 5 | 6  |
| ------- | - | - | ---- | - | - | - | -- |
| valeurs | 3 | 1 | 6    | 5 | 2 | 2 | 4  |
| avant   |   |   | i/ip |   |   |   | vp |

- L'algorithme continue ainsi jusqu'à l'avant dernier indice (le pivot est
exclu de la comparaison avec lui même) :

| indices | 0 | 1 | 2 | 3  | 4 | 5 | 6  |
| ------- | - | - | - | -- | - | - | -- |
| valeurs | 3 | 1 | 2 | 5  | 6 | 2 | 4  |
| avant   |   |   |   | ip | i |   | vp |

Puis :

| indices | 0 | 1 | 2 | 3 | 4  | 5 | 6  |
| ------- | - | - | - | - | -  | - | -- |
| valeurs | 3 | 1 | 2 | 2 | 6  | 5 | 4  |
| avant   |   |   |   |   | ip | i | vp |

Enfin, la valeur pivot est inversée avec celle de `tab[ip]` :

| indices | 0 | 1 | 2 | 3 | 4  | 5 | 6  |
| ------- | - | - | - | - | -  | - | -- |
| valeurs | 3 | 1 | 2 | 2 | 4  | 5 | 6  |
| avant   |   |   |   |   | ip |   |    |

La récursion est effectuée sur les sous-tableaux `[3, 1, 2, 2]` et `[5, 6]`
(la valeur pivot est à sa place définitive).


## Complexité

L'efficacité en moyenne est on `ϴ(n.log2(n))`, mais dans le pire cas la complexité
est en `O(n²)`. Cet algorithme n'est donc pas stable.

Le pire cas survient quant la valeur pivot est la plus grande ou petite et
que le partage en deux sous tableaux est disproportionné (un seul élément
d'un côté, les autres de l'autre).


## Code de la fonction de tri

*Cette fonction sert d'enveloppe pour initialiser la sous-fonction récursive.*

```python
from typing import List
import math #pour le calcul de la complexité théorique

def triRapide(tab: List[int]) -> List[int]:
    """
    trie le tableau selon la méthode du tri rapide, par ordre croissant
    @param tab le tableau de valeurs, en entrée-sortie (par adresse)
    @return le tableau trié par ordre croissant (pour doctests)
    >>> triRapide([])
    []
    >>> triRapide([1])
    [1]
    >>> triRapide([2, 1])
    [1, 2]
    >>> triRapide([1, 3, 2])
    [1, 2, 3]
    >>> triRapide([4, 1, 3, 2])
    [1, 2, 3, 4]
    >>> triRapide([4, 2, 4, 2, 1, 4, 4])
    [1, 2, 2, 4, 4, 4, 4]
    """
    def _triRapide(tab: List[int], inf: int, sup: int):
        cout += 1            #CPLX
        if inf < sup - 1: #cas d'arrêt (condition pour continuer)
            #partition:
            vp = tab[sup - 1]
            ip = inf
            for i in range(inf, sup - 1):
                cout += 1   #CPLX
                if tab[i] < vp: #échange
                    if i != ip: #sauf si c'est inutile (test facultatif)
                        tab[i], tab[ip] = tab[ip], tab[i]
                    ip += 1
            tab[sup - 1], tab[ip] = tab[ip], tab[sup - 1] #pivot
            #division:
            _triRapide(tab, inf, ip)
            _triRapide(tab, ip + 1, sup)
    
    global cout #CPLX
    cout = 0    #CPLX
    _triRapide(tab, 0, len(tab))
    return tab


if __name__ == "__main__":
    import doctest; doctest.testmod()
	
    tab = [4, 7, 4, 8, 5, 9, 6] #meilleur cas
    print("Avec tab =", tab) 
    triRapide(tab)
    print(tab)
    n = len(tab)
    print("- complexité théorique n.log2(n) : " + str(int(n*math.log2(n))))
    print("- complexité pire cas : " + str(int((n**2 - n)/2)))
    print("- complexité effective : " + str(cout))
    
    tab = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] #déjà trié
    print("Avec tab =", tab) 
    triRapide(tab)
    print(tab)
    n = len(tab)
    print("- complexité théorique n.log2(n) : " + str(int(n*math.log2(n))))
    print("- complexité pire cas : " + str(int((n**2 - n)/2)))
    print("- complexité effective : " + str(cout))
```